/*
An array of size n+1 has integers only from 1 to n. The integers 1 to n can be present 0 or more times in the array. Find the first repeating element in the array.
Restrictions: O(n) algo required. Cannot use extra space(not even O(1)).
*/

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

int findFirstDuplicate(int num[], int size)
{
    int lo = 0, hi = size-1;
    while(lo < hi) {
        int mid = lo + (hi-lo)/2;
        if (num[mid] > mid+1) hi = mid;
        else lo = mid+1;
    }
    return lo + 1;
}

int main(int argc, char **argv)
{
    int A[] = {4,6,7,7,7,8,9};
    cout << findFirstDuplicate(A, sizeof(A)/sizeof(int)) << endl;
}
